package algorithm.leetcode.medium;


/*
 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。
 调用 next() 将返回二叉搜索树中的下一个最小的数。
 */

import java.util.ArrayList;
import java.util.List;

/**
 * @author jack.wu
 * @version 1.0
 * @date 2020/12/9
 */
public class Question173 {

    public static void main(String[] args) {

    }


    /**
     * 思路 中序遍历
     */
    class BSTIterator {

        private List<Integer> nodeList;
        private int size;

        public BSTIterator(TreeNode root) {
            this.nodeList = new ArrayList<>(10);
            this.size = -1;
            fillNodeListForRootNode(root);
        }

        private void fillNodeListForRootNode(TreeNode root) {
            if (root == null) {
                return;
            }
            fillNodeListForRootNode(root.left);
            nodeList.add(root.val);
            fillNodeListForRootNode(root.right);
        }

        public int next() {
            return nodeList.get(++size);
        }

        public boolean hasNext() {
            // 这里使用 size + 1 而不使用 ++size 因为优先级
            return size + 1 < nodeList.size();
        }
    }


    public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }

}
